package com.kitty.record.kittyalgorithm.basicalgorithm;

import java.util.Arrays;

/**
 * 插入排序
 *通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应的位置并插入。
 *
 *
 *
 * @Author SHEN
 * @Date 2020/12/30
 */
public class InsertSort {

    public static void main(String[] args) {
        int[] a1 = new int[]{9,8,6,3,4,5,2,6,7};

        insertSort(a1);

        System.out.println("a1 = " + Arrays.toString(a1));

    }

    public static void insertSort(int[] array){

        for (int i = 1; i < array.length; i++) {

            int insertVal = array[i];

            int index = i-1;
            //循环移动有序序列，让对应的值插入到核实的位置
            while(index >= 0 && insertVal < array[index]){
                array[index+1] = array[index];
                index--;
            }
            array[index + 1] = insertVal;
        }
    }
}
